package interview;

import java.util.LinkedList;

public class interview_02_04 {
    public ListNode partition(ListNode head, int x) {
        LinkedList<Integer> list=new LinkedList<>();
        ListNode p=head;
        while(p!=null){
            if(p.val<x){
                list.addFirst(p.val);
            }
            else list.add(p.val);
            p=p.next;
        }
        p=head;
        while(p!=null){
            p.val=list.removeFirst();
            p=p.next;
        }
        return head;
    }
}
